1. Field of the Invention
This invention relates to signal redundancy reduction coding and decoding for use in conjunction with facsimile document transmission systems, and more particularly to a method and apparatus for real time, one dimensional coding and transmission of binary signals where an original document is scanned so as to be resolved into picture elements (pels) of a first level (for example black) and a second level (for example white).
2. Description of the Prior Art
Facsimile transmission is a method of transmitting documents by reducing the document to an electronic image which may be readily transmitted over conventional channels and reconstructed at a remote location. In recent years the method and apparatus for accomplishing facsimile transmission have become increasingly well developed and widely used. The amount of facsimile signal obtained by scanning an original document is enormous. For example, sampling a document of 81/2.times.11 inch paper with a sampling density of 100 pels per inch in both the primary and secondary scanning directions results in a binary representation in the amount of approximately one million pels.
Redundancy reduction coding schemes have been proposed for highly efficient transmission of facsimile signals. These schemes all take advantage of the redundancy within the facsimile signal and reduce the number of bits to be transmitted or stored without impairment of the picture quality. Examples of facsimile systems using redundancy reduction coding to minimize the required data for defining the document are disclosed in U.S. Pat. No. 4,156,880, entitled: Method For Transmitting a Facsimile Signal by Sequential Edge Differential Coding, issued to Toyomichi Yamada, May 29, 1979, and U.S. Pat. No. 4,136,363, entitled: Truncated Run Length in Coding, issued to Amitabh Saran, Jan. 23, 1979. The Yamada patent, in particular, includes a detailed description of the prior art relating to data transmission coding schemes and said description is by reference incorporated herein.
In recent years, it has become increasingly important to improve the resolution of documents which are transmitted by facsimile transmission techniques. These increased requirements for accurate and detailed resolution of facsimile transmission documents have resulted in an explosion of the information required to define a single document page. For example, if the sampling density is increased from 100 pels/inch to 300 pels/inch in both the primary and secondary scanning directions, the binary representation of an 81/2.times.11 inch document reaches approximately 8,400,000 bits. This explosion of information has greatly increased the need for data reduction and further, perhaps even more importantly, the need to be able to deal with such enormous amounts of data on a real time basis. It can readily be understood that failure to deal with such data on a real time basis would produce staggering amounts of data to be stored prior to reduction.
Accordingly, the present invention is directed to a data compression scheme with a primary concern for the speed with which the data is handled and transmitted. While many of the sophisticated data compression systems of the prior art deal mainly with techniques for reducing the data to the smallest accurate definition, the main concern of the present invention is not optimum reduction of data but, more importantly, efficient compression of the data on a real time basis.